Memory referencing in a computer system typically follows one of two paradigms; a physical address model or a virtual address model. The physical model is most direct and therefore fast. A limitation of the physical model is the requirement that programs be written to run within the bounds of the particular computer system physical memory space and at specific locations within that physical memory space. The virtual model is much more flexible, but the time required to translate from virtual space to physical space at run time can contribute detrimentally to the general performance of the computer system.
The definition of physical memory is the implementation, in physical devices, of a storage medium such that storage locations are physically contiguous from "0", or the lowest address, to some upper bound that is limited by the nature of the storage medium, the storage medium may allow random access to the individual storage locations or sequentially to the individual storage locations depending upon the nature of the physical storage medium. A computer system memory storage medium is typically implemented as Dynamic random Access Memory integrated circuits, the granularity of memory is also important to this discussion. Granularity refers to the smallest physical number of memory bits that can be addressed by the computer system hardware. This is defined as a memory word and the width in bits is dictated by the physical architecture of the computer system. A memory word may consist of one or more bytes (eight bit words) of data.
There are two general models of mapping program data and program code structures onto a physical memory space. These are the segmentation model and the paged model. An important definition is that of a "block". A block of memory is the amount of physical memory large enough to contain a segment, in the segmented model, or one page, in the paged model.
The segmentation model is the most space efficient since it reserves exactly the amount of physical space, in words, required to exactly store the program data or code structures. A big disadvantage to the segmentation model is the requirement to map the entire virtual segment into a block of contiguous physical space. Large program code and data structures tend to limit the number of different programs that can co-exist in physical memory due to virtual segment size requirements, and therefore limit the multi-processing capability of the computer system.
The paged model requires that physical memory be broken down into chunks of uniformly sized blocks of memory, called pages, each block containing the same amount of contiguous physical memory. The page size (block size) is usually fixed by the physical architecture of the computer system and is typically in power of 2 sizes (i.e. a page may be a block of 256, 512, 1024, etc. words of contiguous physical memory.). An advantage of the paged model is that it eliminates the requirement of maintaining an entire program data or code structure in physical memory; the individual pages that make up the program data or code structure may be located in any order anywhere in physical memory. The paging model allows for efficient multi-programming by allowing some of the pages of a program's is code or data structure to be swapped out of physical memory and be replaced by pages from some other unrelated program. The paged memory model allows implementation of efficient virtual to physical address translation mechanisms if page size is a power of 2. A major disadvantage of the paged model is the waste of physical memory space that occurs when program code and data structures are smaller than the space required for a page.
The ideal implementation of a physical model would allow some combination of the segmented and paged models. This invention defines the embodiment of an efficient mechanism that implements a combined paged-segmented model and specifically the mechanism for the efficient processing of bi-directional page boundary crossings. This invention allows the efficiency of smaller non-swappable blocks and the resulting performance improvements to multiprocessing, along with the conversation of memory space allowed by the segmented model.
The logical implementation of a virtual memory system that would be a user of the paged-segmented physical model will typically use a logical structure called a "Pointer" to provide the virtual address in the virtual address model. The pointer is an abstract device that allows a program to reside in virtual rather than physical memory space and therefore detached from the physical implementation. This allows for efficient multi-processing since the only effect that physical memory size has on the computing environment is one of performance.
Translations of virtual addresses to physical addresses in a paged memory system are typically implemented in special mechanisms known in the art as Translation Look-a-side Buffers. These can be implemented in special hardware structures to improve efficiency, but sometimes are implemented as "soft" code routines. The mechanism in this embodiment consists of a unique implementation of a content addressable memory (CAM) that allows for efficient translation of paged segments and onpaged segments in hardware.
This invention utilizes this CAM, now to be called the Actual Segment Descriptor Associative Memory (ASDAM) to implement the paged-segmented model. The pointer, that is the virtual address, is a logical structure that contains an index value, called an "ASD number", and a displacement that will e utilized to provide the final information required to point to the first physical word in a physical block of memory. The "ASD number", from the pointer, is an index into a special structure existing in physical memory that is known as the Actual Segment Descriptor Table. An entry in this table is really a structure that consists of four words (a word in this embodiment contains six bytes of data).
The "ASD Number" is the means of identifying a block of contiguous physical memory. Every block of contiguous physical memory has a unique ASD Number, assigned by the operating system. The correspondence between the ASD Number and the physical location of the block is provided by a four word entry in the ASD Table. An ASD Number in this embodiment is 23 binary bits in length, limited by the allowable field width of the ASD Number field within the pointer. The displacement field, mentioned previously, consists of a 20 bit wide field that is also limited by the allowable field width of the Displacement field within the pointer.
In this embodiment, the physical blocks of memory are called "Actual Segments". In this embodiment, an Actual Segment may refer to a block containing contiguous words of physical memory that may be less or more than one page size. The blocks containing more than one page size of words are reserved for special cases and are not typical. This embodiment allows for a mixture of "pure" virtual segments along with "paged" virtual segments; with the term "virtual segments" referring to the virtual addressing environment. A "pure" virtual segment acts as defined by the segmented model. This allows the efficiency of the pure segmented model for virtual segment sizes that would be smaller than a page size.
An example of a "pure" virtual segment would e a 100 word actual segment (assuming a page size of 4096 words). As will be shown, this pure virtual segment, which consists of one actual segment, can be located in physical memory by means of it's ASD Number from it's pointer utilizing the proper entries in the ASD Table.
For program data and code structures larger than a page size, a paged-segmented model is implemented. This means that a data or code virtual segment, represented in the paged-segmented model, actually consists of a modulo page-size-number of pages (actual segments) terminated by an actual segment of less than one page-size number of words. A paged-segmented example would be a data virtual segment consisting of a 9233 word virtual segment actually composed of two actual segment pages (assume 4096 word page size) and terminated with a 1041 word actual segment. Each of the two page size actual segments, along with the 1041 word actual segment have a unique ASD Number and corresponding ASD Table entry. Because of this, neither the actual segments containing the two pages nor the termination actual segment containing the 1041 remaining words are required to be contiguous with one another. The implementation of the ASDAM mechanism and pointer updating mechanisms allow for efficient access to this complex structure.
The paged-segmented model is implemented in this embodiment via a hierarchical pointer structure. Just as each virtual segment is referenced by a virtual pointer, each page is also referenced by it's own virtual pointer. This results in an overall environment where a pure virtual segment is addressed by only a single virtual pointer, whereas a paged virtual segment, represented by the paged-segmented model, is a two level hierarchy of virtual pointers; the first level consisting of a single virtual pointer representing the overall virtual segment, and the second level consisting of virtual pointers representing the pages within that virtual segment. The collection of virtual pointers representing the pages of the virtual segment are contained in an actual segment known as the "Page Table". The virtual pointers continued in the Page Table each contain an ASD Number that references a unique ASD table entry representing each page. The Page Table actual segment is referenced via an entry in the ASD Table similar to any other actual segment. In this embodiment the first level pointer, representing the virtual segment, contains an ASD Number that references the page Table via the ASD Table while the displacement field within the first level pointer indirectly references the desired physical word. The pointer hardware mechanism of this embodiment efficiently allows the transformation from a virtual segment address via two levels of virtual pointers to the final physical address required at run time.